系列文章目录：FPGA原理与结构（0）——目录与传送门

        进位链CARRY在FPGA中本质上就是解决加减法进位问题的元器件，在学习进位链之前，我们需要对数字电路的加减法做一个简单的回顾。

        在学习组合电路的时候，半加器作为一个非常经典的电路设计是初学者避不开的一个话题。其本质就是实现了不带进位输入的二进制加法运算，其真值表如下

        根据真值表我们可以很容易得出：

                                                                carry = a & b ;

                                                                sum = a ^ b ;

        对应的电路结构如下:        

        对应真值表不同的输入情况如下：

        有了半加器我们就解决了一位二进制数的加法问题，但是这显然还是不够的，要想实现多位二进制数的加法问题，我们就必须在现有电路的基础上进行改进，首先就是要引入进位输入。

        和之前一样，我们还是先给出真值表

         根据真值表给出逻辑式：                                                  Sum = A ^ B ^ Cin;                                                  Cout = ( A & B ) | (( A ^ B ) & Cin);

        这里再去搭电路就有点浪费时间了，我们用vivado的rtl分析来观察电路结构

        在有了半加器和全加器之后，我们就算是有了搭建多位二进制加法器的基本元件，接下来的问题就是怎么完成全加器之间的级联问题。

        我们以搭建一个4位的加法器为例，这种加法器的设计思路非常的简单，就是把上一个加法器的进位连接到下一个加法器的进位输入端，具体的设计电路如下：

         用这样的设计思路，我们可以实现任意位数的加法器。这里我们在第一位使用的是半加器，我们也可以把这个半加器换成全加器来实现，只要保证第一位的Cin为0就行：

         我们来看以下行波进位加法器是如何运行的，首先我们假设初始状态下所有的位都是0

        接下来我们来进行一个运算：0111+0001 = 01000 ，但是在经过一个全加器(FA)的时延后，结果是00110

        这当然不意味着我们设计的加法器是错误的，只是因为想要得到正确的结果，我们还需要更多的时间：

        可以看到在经过4个FA的时延之后，我们得到了正确的答案，但是这显然暴露出一个很大的问题，那就是行波进位加法器需要很大的处理时间才能得到正确答案，而且我们很容易预见到，这个处理时间会随着我们运算位数的增加而增加。因为高位的运算必须等待低位的运算完成， 这样造成了整个加法器的延迟时间很长。 

        很显然我们之前讨论的行波进位加法器在效率和时延问题上有着很大的不足，那么有没有更加高效的加法器设计呢？要设计出更高效的加法器，我们首先要明确，造成行波进位加法器效率问题的根本原因在于它的高位运算必须等待低位的运算完成，这样等于同一时间只有一个全加器能够进行有效运算，其本质是在进行一个串行的运算，那么我们很自然地想到能不能把这个串行的运算转换成并行处理，也就是能否提前计算出“进位输出信号”？

        我们可以用前一个全加器的参数来表示后面的进位输出（Cout），即：

        由此来表示4个全加器的进位输出为： 

        最终我们需要得到的是C4，经过换算C4的这些参数，全部已知！并不需要前一个全加器运算输出，由此我们得到了提前计算进位输出的方法， 用这样的方法实现了加法器就被称为超前进位加法器（Carry-Lookahead Adder，CLA）。

        根据上面的优化算法，我们重新绘制了CLA的布线方式

        这样设计出来的超前进位加法器显然在效率上更加有优势，但是也有着自己的问题，最明显的就是设计起来的复杂度大大增加了，而且也是随着运算位数的增加而显著增加。 

        说了一大堆加法器的前置知识，接下来进入我们的整体，FPGA中的进位链，进位链的使用其实是非常广泛的（或者说所有有资格在FPGA单独成为一个器件的元件应用都很广泛），举个简单的例子，大家对于计数器应该并不陌生，那既然都有计数器了，就必然已经用到了进位链。我们知道CLB在FPGA中最为丰富，在7系列的FPGA中，一个CLB中有两个Slice，一个Slice中包含4个LUT6、3个数据选择器MUX、1个独立进位链（Carry4，Ultrascale是Carry8）和8个触发器。这里我们来谈论Carry4。在CLB中，除了函数发生器之外，还提供了专用的快速超前进位逻辑，以slice中执行快速算术加法和减法。 7系列FPGA CLB具有两个独立的进位链，如下图所示， 进位链可级联以形成更宽的加/减逻辑。

CI：        上一个CARRY4的进位输出，位宽为1，可以级联形成更大规模的运算逻辑

CYINT： 进位的初始化值，位宽为1，0为加法，1为减法

DI：        数据的输入（两个加数的任意一个），位宽为4；

S：         两个加数的异或，位宽为4；

O：         加法/减法结果输出，位宽为4，它们连接到slice AMUX / BMUX / CMUX / DMUX输出；

CO：      进位输出，位宽为4，这里的进位是每一位的进位，比如CO[0]就表示最低位的加法进位，这样就可以实现小于4bit的加减法。

         仅仅看端口含义显然不足以帮助我们理解CARRY4的具体工作原理，接下来我们来看CARRY4的内部结构。

        从图中我们可以观察到，其实CARRY4是由相同的4个单元构成的，如下图中红色部分标注的就是其中的一个基本单元：

这个单元我们本质上可以理解成一个全加器：

CIN = 进位输入（当它在最低位时，置0做加法，置1做减法）

S0 = A0 ^ B0 （这里和全加器中的S有些区别），它来自LUTA的O6

O0 = S0 ^ CIN = A0 ^ B0 ^ CIN（这里的O才是全加器的S），它来自LUTA的O5或外面外部输入AX

DI0 = A0 或者 B0 （这里指的是两个加数中的任意一个，它的作用要配合S0）

AX 是预置数，这里我们不过多关注。

这里面还包含一个MUX逻辑，这里的逻辑是：S = 0，输出为左侧输入，S = 1，输出为右侧输入。

我们知道产生进位的条件在A B以及 CIN中有两个或两个以上的1。

(1)当S=0时，有两种情况,即两个加数都为0和两个加数都为1。此时，MUX选择DI作为数据输入，CO的结果由DI决定。因为S0=0时，DI为0等价于A0，B0，CO0都为0。DI为1等价于A，B，CO都为1。

(2)当S=1时，即A与B中有1个为1。此时，MUX选择CIN作为数据输入，CO的结果由CIN决定。因为S=1时，A与B中只有1个1，还缺1个1才能进位，进位所需的那个1就看低位来的进位CIN是不是1了。

这样从结构上来看，和我们之前谈到过的超前进位加法器就很像了。

        我们以一个8位的加法运算为例

综合后的结果如下：

        可以看到由于是8位的加法运算，所以这里用到了两个CARRY4 。

        有关进位链的内容就大概说到这里，再补充两点。

        （1）进位链级联数有限制，它取决于当前列SLICE的个数，而且不能跨逻辑区域。逻辑区域里进位链最大级数等于绿框中的SLICE的高度（如果是多位全加器的位宽就是SLICE的高度x4，因为1个SLICE里有4个级联的全加器）。

        （2）进位链级联数越多，造成的路径延迟就会越大，这样会让时序十分的紧张。所以在使用进位链时要综合考虑级联数与整个系统速率的关系。例如在设计位宽较大的计数器，可以选择用DSP替换，也可以选择将位宽分隔。（如32位计数器，可将它分成高16位，与低16位，低16位计数到16'hffff，高16位计数才+1） 

306 - 加法器的优化——超前进位加法器（Carry-Lookahead Adder，CLA）

FPGA从入门到精通(5) - 进位链